package algorithms.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树（二叉排序树）
 * 
 * 特征：
 * <li>空树</li>
 * <li>非空树，左子树的key均小于父节点，右子树的key都大于父节点的key，此特性是递归的。</li>
 * 
 * @author shaoyuxia
 *
 * @param <K>
 */
public class BinarySearchTree<K extends Comparable<K>> extends BinaryTree<K> {

	public BinarySearchTree(K key) {
		super(key);
	}

	public BinarySearchTree() {
	}

	@Override
	protected void insert(BinaryNode<K> baseNode, BinaryNode<K> node) {
		// 大于节点
		if (node.getKey().compareTo(baseNode.getKey()) > 0) {
			// right sub tree
			if (baseNode.getRight() == null) {
				baseNode.setRight(node);
				node.setParant(baseNode);
			} else {
				insert(baseNode.getRight(), node);
			}
			// 小于等于节点,如果相等节点不做处理即可去除重复节点
		} else {
			// left sub tree
			if (baseNode.getLeft() == null) {
				baseNode.setLeft(node);
				node.setParant(baseNode);
			} else {
				insert(baseNode.getLeft(), node);
			}
		}
	}

	@Override
	public BinaryNode<K> getNodeByKey(K key) {
		return binarySearch(rootNode, key);
	}

	public BinaryNode<K> getNodeByKey2(K key) {
		return binarySearchWithLoop(rootNode, key);
	}

	/**
	 * 获取key最小节点
	 * 
	 * 不用递归
	 * 
	 * @return
	 */
	public BinaryNode<K> getMinNode() {
		return minNodeInTree(this.rootNode);
	}

	private BinaryNode<K> minNodeInTree(BinaryNode<K> baseNode) {
		while (baseNode != null && baseNode.getLeft() != null) {
			baseNode = baseNode.getLeft();
		}
		return baseNode;
	}

	/**
	 * 获取key最大节点
	 * 
	 * 不用递归
	 * 
	 * @return
	 */
	public BinaryNode<K> getMaxNode() {
		BinaryNode<K> begin = this.rootNode;
		while (begin != null && begin.getRight() != null) {
			begin = begin.getRight();
		}
		return begin;
	}

	/**
	 * @return the rootNode
	 */
	public BinaryNode<K> getRootNode() {
		return rootNode;
	}

	public void setRootNode(BinaryNode<K> node) {
		this.rootNode = node;
	}

	// 排序二叉树的查找（递归）
	protected BinaryNode<K> binarySearch(BinaryNode<K> baseNode, K key) {
		if (baseNode != null) {
			// System.out.println("basekey2Compare:" + baseNode.getKey());
			if (key.compareTo(baseNode.getKey()) == 0) {
				return baseNode;
			} else if (key.compareTo(baseNode.getKey()) > 0) {
				// System.out.println("right");
				// in right sub tree
				return binarySearch(baseNode.getRight(), key);
			} else {
				// in left sub tree
				// System.out.println("left");
				return binarySearch(baseNode.getLeft(), key);
			}
		} else {
			return null;
		}

	}

	// 排序二叉树的查找（循环）
	protected BinaryNode<K> binarySearchWithLoop(BinaryNode<K> baseNode, K key) {
		while (baseNode != null && baseNode.getKey().compareTo(key) != 0) {
			if (key.compareTo(baseNode.getKey()) > 0) {
				baseNode = baseNode.getRight();
			} else {
				baseNode = baseNode.getLeft();
			}
		}
		return baseNode;

	}

	/**
	 * 返回中序序列的字符串
	 */
	@Override
	public String toString() {
		return this.rootNode.inorderTraversing();
	}

	/**
	 * 获取键值的有序列表
	 * 
	 * @return
	 */
	public List<K> getSortedKeyList() {
		List<K> list = new ArrayList<>(getSize());
		// 中序遍历排序二叉树
		inOrderTraversing(rootNode, list);
		return list;
	}

	/**
	 * 中序遍历节点：左-父-右 <br>
	 * 按此序遍历出来的结果是一个有序线性集合，存于list中
	 * 
	 * @param node
	 * @param list
	 */
	private void inOrderTraversing(BinaryNode<K> node, List<K> list) {
		if (node != null) {
			if (node.getLeft() != null) {
				inOrderTraversing(node.getLeft(), list);
			}
			list.add(node.getKey());
			if (node.getRight() != null) {
				inOrderTraversing(node.getRight(), list);
			}
		}
	}

	@Override
	public void deleteNodeByKey(K key) {
		delete(this.rootNode, key);

	}

	protected void delete(BinaryNode<K> basenode, K key) {
		if (basenode != null) {
			if (key.compareTo(basenode.getKey()) > 0) {
				delete(basenode.getRight(), key);
			} else if (key.compareTo(basenode.getKey()) < 0) {
				delete(basenode.getLeft(), key);
			} else {
				BinaryNode<K> parent = basenode.getParant();
				// 无子节点
				if (basenode.getLeft() == null && basenode.getRight() == null) {
					// 无子节点有无父节点，只能是独立的根节点
					if (parent == null) {
						this.rootNode = null;
					} else {
						if (isLeftChild(parent, key)) {
							parent.setLeft(null);
						} else {
							parent.setRight(null);
						}
					}
					// 无左子树，有右子树
				} else if (basenode.getLeft() == null) {
					if (parent == null) {
						this.rootNode = basenode.getRight();

					} else {
						if (isLeftChild(parent, key)) {
							parent.setLeft(basenode.getRight());
						} else {
							parent.setRight(basenode.getRight());
						}
					}

					// 无右子树，有左子树
				} else if (basenode.getRight() == null) {
					if (parent == null) {
						this.rootNode = basenode.getLeft();

					} else {
						if (isLeftChild(parent, key)) {
							parent.setLeft(basenode.getLeft());
						} else {
							parent.setRight(basenode.getLeft());
						}
					}
					// 有左右子树,此处的处理逻辑是使用右子树的最小节点替换baseNode，
					// 还有一种对称的方式是使用左子树的最大节点替换
				} else {
					BinaryNode<K> rightTree = basenode.getRight();
					BinaryNode<K> minInRight = minNodeInTree(rightTree);
					// 右子树只有一个节点
					if (basenode.getRight() == minInRight) {
						minInRight.setLeft(basenode.getLeft());
						if (isLeftChild(parent, key)) {
							parent.setLeft(minInRight);
						} else {
							parent.setRight(minInRight);
						}
					} else {
						// 把最小节点切下替换到basenode的位置
						basenode.setKey(minInRight.getKey());
						basenode.setRight(rightTree);
						parent = minInRight.getParant();
						if (isLeftChild(parent, minInRight.getKey())) {
							parent.setLeft(null);
						} else {
							parent.setRight(null);
						}
					}
				}
			}
		}

	}

	private boolean isLeftChild(BinaryNode<K> parent, K key) {
		if (parent.getLeft().getKey().equals(key)) {
			return true;
		}
		return false;
	}

	@Override
	public void rotateLeft(K key) {
		BinaryNode<K> oldNode = getNodeByKey(key);
		BinaryNode<K> newNode = null;
		if (oldNode != null && (newNode = oldNode.getRight()) != null) {
			// 左旋右上位，新主之左移到旧主之右，新主之新左为旧主
			BinaryNode<K> parent = oldNode.getParant();
			// BinaryNode<K> oldleft = oldNode.getLeft();
			BinaryNode<K> newLeft = newNode.getLeft();
			// BinaryNode<K> newRight = newNode.getRight();
			if (parent == null) {
				// root
				this.rootNode = newNode;
			} else {
				if (isLeftChild(parent, oldNode.getKey())) {
					parent.setLeft(newNode);
				} else {
					parent.setRight(newNode);
				}
			}
			// 新主之左移到旧主之右
			oldNode.setRight(newLeft != null ? newLeft : null);
			// 新主之新左为旧主
			newNode.setLeft(oldNode);
		}

	}

	@Override
	public void rotateRight(K key) {
		BinaryNode<K> oldNode = getNodeByKey(key);
		BinaryNode<K> newNode = null;
		if (oldNode != null && (newNode = oldNode.getLeft()) != null) {
			// 右旋左上位，新主之右移到旧主之左，新主之新右为旧主
			BinaryNode<K> parent = oldNode.getParant();
			// BinaryNode<K> oldleft = oldNode.getLeft();
			BinaryNode<K> newRight = newNode.getRight();
			if (parent == null) {
				// root
				this.rootNode = newNode;
			} else {
				if (isLeftChild(parent, oldNode.getKey())) {
					parent.setLeft(newNode);
				} else {
					parent.setRight(newNode);
				}
			}
			// 新主之右移到旧主之左
			oldNode.setLeft(newRight != null ? newRight : null);
			// 新主之新左为旧主
			newNode.setRight(oldNode);
		}

	}

}
